package com.ting.test.algorithms.大厂刷题班;

import com.ting.test.algorithms.二叉树.TreeNode;

/**
 *
 */
public class 二叉树最大路径和 {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(2);
        int sum = process(node).maxPathSum;
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return null;
        }

        Info left = process(node.getLeft());
        Info right = process(node.getRight());

        //1. 必须包含头结点的最大路径和
        int maxPathSumFromHead = node.getVal();//可能只有他自己
        if (left != null) {
            maxPathSumFromHead = Math.max(maxPathSumFromHead, left.maxPathSumFromHead + node.getVal());//只有他自己+左树
        }
        if (right != null) {
            maxPathSumFromHead = Math.max(maxPathSumFromHead, right.maxPathSumFromHead + node.getVal());//只有他自己+有树
        }
        if (right != null && left != null && left.maxPathSumFromHead > 0 && right.maxPathSumFromHead > 0) {
            //只有他自己+有树+左树
            maxPathSumFromHead = Math.max(maxPathSumFromHead, left.maxPathSumFromHead + right.maxPathSumFromHead + node.getVal());
        }

        int maxPathSum = node.getVal();//自己是整个树的最大路径和
        if (left != null) {
            maxPathSum = Math.max(maxPathSum, left.maxPathSum);//只有左树
        }
        if (right != null) {
            maxPathSum = Math.max(maxPathSum, right.maxPathSum);//只有右树
        }

        maxPathSum = Math.max(maxPathSum, maxPathSumFromHead);//比较谁最大

        return new Info(maxPathSum, maxPathSumFromHead);
    }

    public static class Info {
        int maxPathSum;//整体的最大路径和
        int maxPathSumFromHead;//必须从头结点出发的最大路径和

        public Info(int maxPathSum, int maxPathSumFromHead) {
            this.maxPathSum = maxPathSum;
            this.maxPathSumFromHead = maxPathSumFromHead;
        }
    }
}
